package com.acwing.partition8;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AC734能量石 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int t = Integer.parseInt(s[0]);
        List<EnergyStone[]> energyStoneList = new ArrayList<>(t);
        while (t-- > 0) {
            int n = Integer.parseInt(reader.readLine().split("\\s+")[0]);
            EnergyStone[] energyStones = new EnergyStone[n];
            for (int i = 0; i < n; i++) {
                s = reader.readLine().split("\\s+");
                energyStones[i] = new EnergyStone(Integer.parseInt(s[0]), Integer.parseInt(s[1]), Integer.parseInt(s[2]));
            }
            energyStoneList.add(energyStones);
        }
        List<Integer> answer = dynamicProgramming(energyStoneList);
        for (int i = 0; i < answer.size(); i++) writer.write("Case #" + (i + 1) + ": " + answer.get(i) + "\n");
        writer.flush();
    }

    private static List<Integer> dynamicProgramming(List<EnergyStone[]> energyStoneList) {
        List<Integer> answer = new ArrayList<>();
        for (EnergyStone[] energyStones : energyStoneList) {
            Arrays.sort(energyStones, (o1, o2) -> Integer.compare(o1.s * o2.l, o2.s * o1.l));
            int capacity = 0;
            for (EnergyStone energyStone : energyStones) capacity += energyStone.s;
            //dp[i]表示在给定的时间i内，能得到的最大的能量值
            int[] dp = new int[capacity + 1];
            //01背包，经过贪心算法的预处理后，对于每个石头都有吃和不吃的两种情况
            for (int i = 0; i < energyStones.length; i++) {
                EnergyStone energyStone = energyStones[i];
                for (int j = capacity; j >= energyStone.s; j--) {
                    int prev = j - energyStone.s;
                    dp[j] = Math.max(dp[j], dp[prev] + energyStone.e - prev * energyStone.l);
                }
            }
            answer.add(Arrays.stream(dp).max().getAsInt());
        }
        return answer;
    }

    private static class EnergyStone {
        //吃完当前能量石需要花费的时间、补充的能力、每秒损失的能量
        private int s;
        private int e;
        private int l;

        public EnergyStone(int s, int e, int l) {
            this.s = s;
            this.e = e;
            this.l = l;
        }
    }
}
